import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WelcometoCodeJam {
	private static class IndCount implements Cloneable {
		int ind, count;
		public IndCount(int ind) {
			this.ind = ind;
			count = -1; // -1 means not initialized
		}
		public IndCount clone() {
			try {
				return (IndCount)super.clone();
			} catch(Exception e) {
				e.printStackTrace();
			}
			return null;
		}
		public String toString() {
			return ind + ">" + count;
		}
	}
	private static int numSubSeq(List<List<IndCount>> list, int listInd, int ind) {
		int num = 0;
		if(listInd >= list.size())
			return 1;
		List<IndCount> curList = list.get(listInd);
		for(int i = 0; curList != null && i < curList.size(); i++) {
			if(curList.get(i).ind >= ind) {
				if(curList.get(i).count < 0)
					curList.get(i).count = numSubSeq(list, listInd + 1, curList.get(i).ind + 1);
				num = (num + curList.get(i).count) % 10000;
			}
		}
		return num;
	}
	private static String toString(long n, int d) {
		String s = "" + n;
		while(s.length() < d)
			s = "0" + s;
		return s;
	}
	private static List<IndCount> clone(List<IndCount> list) {
		if(list == null)
			return null;
		List<IndCount> cloneList = new ArrayList<IndCount>();
		for(IndCount item : list)
			cloneList.add(item.clone());
		return cloneList;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader rdr = new BufferedReader(new InputStreamReader(System.in));
		try {
			int N = Integer.parseInt(rdr.readLine());
			for(int n = 1; n <= N; n++) {
				String input = rdr.readLine();
				char[] inputChars = input.toCharArray();
				Map<Character, List<IndCount>> inds = new HashMap<Character, List<IndCount>>();
				for(int i = 0; i < inputChars.length; i++) {
					List<IndCount> list = inds.get(inputChars[i]);
					if(list == null) {
						list = new ArrayList<IndCount>();
						inds.put(inputChars[i], list);
					}
					list.add(new IndCount(i));
				}
				String sub = "welcome to code jam";
				List<List<IndCount>> subInds = new ArrayList<List<IndCount>>();
				char[] subChars = sub.toCharArray();
				for(char c : subChars)
					subInds.add(clone(inds.get(c)));
				int num = numSubSeq(subInds, 0, 0);
				System.out.println("Case #" + n + ": " + toString(num % 10000, 4));
			}
		} finally {
			rdr.close();
		}
	}
}
